#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        vector<vector<int>> profit(nums.size(), vector<int>(2, 0));
        profit[0][1] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            profit[i][0] = max(profit[i - 1][0], profit[i - 1][1]);
            profit[i][1] = profit[i - 1][0] + nums[i];
        }
        return max(profit[nums.size() - 1][0], profit[nums.size() - 1][1]);
    }
};

int main() {
    vector<int> input = {2, 7, 9, 3, 1};
    Solution solution;
    int output = solution.rob(input);
    cout << output << endl;
    return 0;
}